//
//  DynamicPlanning.swift
//  ArithmeticClass15
//
//  Created by xiangzuhua on 2021/2/25.
//
class DynamicPlanning {
    
    /// 根据现有的物品，在背包的最大装载值前提下，怎样装物品才能使背包中物品重量最大
    /// - Parameters:
    ///   - goods: 物品集合，存储的是各个物品的重量
    ///   - capacity: 背包的容量
    /// - Returns: 返回背包中物品重量的最大值
    class func pocketMaxLoad(owned goods:[Int], max capacity: Int) -> Int {
        let count = goods.count
        // 该数组存储在背包中放不同物品的组合，出现的各种不同重量的情况，最多有capacity种情况，如果组合中有这种重量值存在，则将数组中以重量值为角标的值设为true，否则为false
        var hasDoArray = [Bool](repeating: false, count: capacity + 1)
        hasDoArray[0] = true // 第一个要特殊处理，可以选择不放物品，背包重量就是0
        if goods[0] < capacity {// 背包中放第一个物品
            hasDoArray[goods[0]] = true
        }
        
        for i in 1..<count {// 依次放入后续的物品
            for j in (0...(capacity - goods[i])).reversed() {// 反向遍历，
                if hasDoArray[j] == true {
                    hasDoArray[j + goods[i]] = true
                }
            }
        }
        
        for (index,item) in hasDoArray.enumerated().reversed() {
            if item == true {
                return index
            }
        }
        return 0
    }
    
    
    class func pocketMaxLoadWithValue(goods weights: [Int], _ values: [Int], max capacity: Int) -> Int{
        let count = weights.count
        // 存储各种情况下价值的大小
        var status = [[Int]](repeating: [Int](repeating: -1, count: capacity + 1), count: count)
        
        // 对于第一个的情况提前处理
        status[0][0] = 0
        if weights[0] < capacity {
            status[0][weights[0]] = values[0]
        }
        
        // 遍历每一个物品，并将加入和不加入的所有情况的价值大小存入数组
        for i in 1..<count {
            // 第i个物品不加入
            for j in 0...capacity {
                if status[i - 1][j] >= 0 {
                    status[i][j] = status[i - 1][j]
                }
            }
            
            // 第i个物品加入
            for j in 0...(capacity - weights[i]) {
                if status[i - 1][j] >= 0 {
                    let temp = status[i - 1][j] + values[i]
                    if temp > status[i][j + weights[i]] {
                        status[i][j + weights[i]] = temp
                    }
                    
                }
            }
        }
        
        // 找出最大值
        var maxValue = -1
        for i in 0...capacity {
            if status[count-1][i] > maxValue {
                maxValue = status[count - 1][i]
            }
        }
        return maxValue
    }
    
    // 优化版-优化空间复杂度
    class func pocketMaxLoadWithValue2(goods weights: [Int], _ values: [Int], max capacity: Int) -> Int{
        let count = weights.count
        // 存储各种情况下价值的大小
        var status = [Int](repeating: -1, count: capacity + 1)
        
        // 对于第一个的情况提前处理
        status[0] = 0
        if weights[0] < capacity {
            status[weights[0]] = values[0]
        }
        
        for i in 1..<count {
            
            // 第i个物品加入
            for j in (0...(capacity - weights[i])).reversed() {
                if status[j] >= 0 {
                    let temp = status[j] + values[i]
                    if temp > status[j + weights[i]] {
                        status[j + weights[i]] = temp
                    }

                }
            }
        }
        
        // 找出最大值
        var maxValue = -1
        for i in 0...capacity {
            if status[i] > maxValue {
                maxValue = status[i]
            }
        }
        return maxValue
    }
    
    // 练习题-杨辉三角
    class func shortWay(yanghuiTriangle numbers: [[Int]]) -> Int {
        let count = numbers.count
        // 创建一个二维数组，存储三角中按路径从上往下累加的各种组合的值，重合的情况只存储最小值
        var values = [[Int]](repeating: [Int](), count: count)
        for i in 0..<count {
            let arr = numbers[i]
            let count1 = arr.count
            for _ in 0..<count1 {
                values[i].append(0)
            }
        }
        
        // 第一个元素做特殊处理
        values[0][0] = numbers[0][0]
        
        //
        for i in 1..<count {
            let arr = numbers[i]
            let count1 = arr.count
            for j in 0..<(count1 - 1) {
                // 往左边的路劲走
                if values[i][j] == 0 {// 没有值，直接累加赋值
                    values[i][j] = values[i-1][j] + numbers[i][j]
                } else if values[i-1][j] + numbers[i][j] < values[i][j]{// 有值，需要判断谁更小
                    values[i][j] = values[i-1][j] + numbers[i][j]
                }
                
                // 往右边路径走
                if values[i][j + 1] == 0 {
                    values[i][j + 1] = values[i - 1][j] + numbers[i][j + 1]
                } else if values[i - 1][j] + numbers[i][j + 1] < values[i][j + 1] {
                    values[i][j + 1] = values[i - 1][j] + numbers[i][j + 1]
                }
                
            }
        }
        
        // 取最小路径值
        let tempArr = values.last!
        var miniValue = 0
        for i in tempArr {
            if miniValue == 0 {
                miniValue = i
            } else if i < miniValue {
                miniValue = i
            }
        }
        return miniValue
    }
    
    // 练习题-杨辉三角，第二种方法，降低空间复杂度
//    class func shortWay2(yanghuiTriangle numbers: [[Int]]) -> Int {
//        let count = numbers.count// 杨辉三角是个等边三角形，最下层元素个数与层数相等
//        // 创建一个数组，存储从最下层走出杨辉三角的各路径值
//        var values = [Int](repeating: 0, count: count)
//        // 第一个元素做特殊处理
//        values[0] = numbers[0][0]
//        for i in 1..<count {
//            let arr = numbers[i]
//            let count1 = arr.count
//            for j in 0..<count1 - 1 {
//                // 向右
//                values[j + 1] = values[j] + numbers[i][j + 1]
//                // 向左
//                values[j] = values[j] + numbers[i][j]
//            }
//        }
//
//    }
    
    /*
     假设我们有一个 n 乘以 n 的矩阵 w[n][n]。
     矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
     */
    
    /// 求从矩阵的左上角走到右下角的最短距离
    /// - Parameter matrix: 矩阵
    /// - Returns: 最短距离
    class func shortPath(_ matrix:[[Int]]) -> Int {
        let count = matrix.count
        var stepCounts:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: count), count: count)
    
        // 处理初始值
        stepCounts[0][0] = matrix[0][0]
        for i in 1..<count {
            stepCounts[0][i] = stepCounts[0][i - 1] + matrix[0][i]
        }
        for j in 1..<count {
            stepCounts[j][0] = stepCounts[j - 1][0] + matrix[j][0]
        }
        
        for i in 1..<count {
            for j in 1..<count {
                if stepCounts[i][j - 1] + matrix[i][j] <= stepCounts[i - 1][j] + matrix[i][j] {
                    stepCounts[i][j] = stepCounts[i][j - 1] + matrix[i][j]
                } else {
                    stepCounts[i][j] = stepCounts[i - 1][j] + matrix[i][j]
                }
            }
        }
        
        return stepCounts[count - 1][count - 1]
    }
    
    /* 第二节课后思考题
 硬币找零问题，我们在贪心算法那一节中讲过一次。我们今天来看一个新的硬币找零问题。假设我们有几种不同币值的硬币 v1，v2，……，vn（单位是元）。如果我们要支付 w 元，求最少需要多少个硬币。比如，我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元，最少需要 3 个硬币（3 个 3 元的硬币）
 */
    class func minCoinPay(coins kinds: [Int],should pay: Int) -> Int {
        var coinNumbers = [[String]](repeating: [String](repeating: "", count: pay + 1), count: pay)
        // 第一次的数据先做处理
        for value in kinds {
            if value < pay {
                coinNumbers[0][pay - value] = String(value)
            }
        }
        
        for i in 1..<pay {
            for j in 0...pay {
                if coinNumbers[i - 1][j] != "" {
                    for value in kinds {
                        if value == j {
                            coinNumbers[i][j - value] = coinNumbers[i - 1][j] + String(value)
                            return i+1
                        }else if value < j {
                            let newStep = coinNumbers[i - 1][j] + String(value)
                            let lastStep = coinNumbers[i - 1][j - value]
                            if coinNumbers[i - 1][j - value] == "" ||
                                lastStep.count > newStep.count {
                                coinNumbers[i][j - value] = newStep
                            }
                        }
                    }
                }
            }
        }
        return pay
    }
    
    /// 从不同币值的几种硬币中（同一币值的硬币个数不限），选择硬币数量最少的组合去支付总费用
    ///
    /// 假设总费用为9
    /// 使用一个数组（A,下标为0~9），下标代表剩余的未支付的费用，存储的是使用的硬币币值的字符串。
    /// 假如最小币值为1，那么最多支付9次，而且最多存在9种未支付的费用值（1~9），所以遍历9次，
    /// 如果币值种类为[1,3,5]
    /// 首先对数组A预处理，9 -1 = 8，所以在下标8的位置填上“1”（表示使用了币值为1的硬币）
    /// 同理在下标9 - 3 = 6填上“3”，下标4填上“5”。这是对数组A遍历了第1遍。
    /// 然后继续对数组遍历第2遍，最多9遍。第1遍特殊，第2遍和后面的规律一样，看看第2遍是怎么遍历数组的。
    /// 此次遍历，只需要找到数组中有值的位置，角标代表剩余未支付的费用，存储的是已支付的硬币值字符串，
    /// 遍历到下标4，然后分别取1、3、5去与下标4做减法代表再支付一部分费用，
    /// 将得到的值（剩余未支付费用）当做新的下标，如4 - 1 = 3，然后在下标3处 存储下标4中的字符串（“5”）与此次使用的币值字符串（“1”）拼接后得到的字符串“51”，
    /// 即A[3] = "51"。
    /// 在存储得到的字符串的过程中，可能存在将要存储的位置已有值的情况，
    /// 这时需要对比两个值的字符串长度，取最短的那一个存储进去就可以，这里遵循的是使用最少硬币原则。
    /// 当使用不同币种对比完成后，这一次遍历就结束了，然后可以进行第3次和第4次...。
    /// 遍历过程中一旦碰到剩余费用与某个币值相减得0，得出A[0]应该存储的字符串后，操作结束。
    /// 到此，A[0]字符串长度即为最少硬币数，A[0]的值为使用的硬币组合
    /// - Parameters:
    ///   - pay: 需要支付的总费用
    ///   - kinds: 硬币的币值种数
    /// - Returns: 返回使用的最少硬币个数
    class func minimumCoins(to pay: Int, coins kinds: [Int]) -> Int {
        // 下标为使用过某些硬币后剩余的值，存储的是使用过的硬币的数字字符串
        var coinNumbers = [String](repeating: "", count: pay + 1)
        // 第一次的数据先做处理，用总费用减去不同币种，到的角标出存储使用币值的字符串
        for value in kinds {
            if value < pay {
                coinNumbers[pay - value] = String(value)
            }
        }
        
        // 遍历1 ~ pay - 1遍
        for _ in 1..<pay {
            // 探寻数组中的每一个值
            for i in 0...pay {
                if coinNumbers[i] != "" {// 非空字符串为有效值
                    for value in kinds {// 与不同币种做减法
                        if value == i {// 剩余费用等于此刻使用的硬币币值
                            coinNumbers[i - value] = coinNumbers[i] + String(value)
                            return coinNumbers[i - value].count// 返回字符串长度即为使用的硬币数
                        }else if value < i {// 剩余费用得够减才算有效
                            // 剩余费用减去硬币值后，拼接新位置需要存储的字符串
                            let step = coinNumbers[i] + String(value)
                            let newStep = coinNumbers[i - value]// 新位置原来的字符串
                            // 原来字符串为空直接存入新字符串,或者取新旧字符串中最短的一个存入对应位置
                            if newStep == ""
                                || newStep.count > step.count
                            {
                                coinNumbers[i - value] = step
                            }
                        }
                    }
                }
            }
        }
        return pay
    }
    
    // 莱文斯坦距离
    class func lwstDistance(_ string1: [Character], _ string2: [Character]) -> Int{
        let count1 = string1.count
        let count2 = string2.count
        var minDistances = [[Int]](repeating: [Int](repeating: 0, count: count2), count: count1)
        // 处理开头的位置
        if string1[0] == string2[0] {
            minDistances[0][0] = 0
        } else {
            minDistances[0][0] = 1
        }
        // 处理第一行，string1[0]与string2[n]的编辑距离
        for i in 1..<count2 {
            if string1[0] == string2[i] {
                minDistances[0][i] = i
            } else {
                minDistances[0][i] =  minDistances[0][i - 1] + 1
            }
        }
        // 处理第一列，string1[n]与string2[0]的编辑距离
        for i in 1..<count1 {
            if string2[0] == string1[i] {
                minDistances[i][0] = i
            } else {
                minDistances[i][0] = i
            }
        }
        
        for i in 1..<count1 {// 遍历行
            for j in 1..<count2 {// 遍历列
                if string1[i] == string2[j] {
                    minDistances[i][j] = min(minDistances[i][j - 1], minDistances[i - 1][j], minDistances[i - 1][j - 1])
                } else {
                    minDistances[i][j] = min(minDistances[i][j - 1] + 1, minDistances[i - 1][j] + 1, minDistances[i - 1][j - 1] + 1)
                }
            }
            
        }
        
        return minDistances[count1 - 1][count2 - 1]
        
    }
    // 最长公共子串
    class func longestCommonSubstring(_ string1: [Character], _ string2: [Character]) -> Int{
        let count1 = string1.count
        let count2 = string2.count
        var maxSubstring = [[Int]](repeating: [Int](repeating: 0, count: count2), count: count1)
        // 处理maxSubstring[0][0]
        if string1[0] == string2[0] {
            maxSubstring[0][0] = 1
        } else {
            maxSubstring[0][0] = 0
        }
        // 第一列
        for i in 1..<count1 {
            if string1[i] == string2[0] {
                maxSubstring[i][0] = 1
            } else {
                maxSubstring[i][0] = maxSubstring[i - 1][0]
            }
        }
        
        // 第一行
        for i in 1..<count2 {
            if string1[0] == string2[i] {
                maxSubstring[0][i] = 1
            } else {
                maxSubstring[0][i] = maxSubstring[0][i - 1]
            }
        }
        
        for i in 1..<count1 {// 行数
            for j in 1..<count2 {// 列数
                if string1[i] == string2[j] {
                    maxSubstring[i][j] = max(maxSubstring[i - 1][j - 1] + 1, maxSubstring[i - 1][j], maxSubstring[i][j - 1])
                } else {
                    maxSubstring[i][j] = max(maxSubstring[i - 1][j - 1], maxSubstring[i - 1][j], maxSubstring[i][j - 1])
                }
            }
        }
        
        return maxSubstring[count1 - 1][count2 - 1]
    }
    
    /*
     我们有一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。
     */
    /// 这个问题可以转化成求最长公共子串，可以先将这一串数字排序，将排序后的数子序列与原数字序列对比，
    /// 求出最长公共子串长度
    class func increasingSubsequence(for sequence: [Character]) -> Int{
        let ascSequence = sequence.sorted { $0<$1 }
        return longestCommonSubstring(sequence, ascSequence)
    }
    
    
}
